package mine.code.plan.spring2021;

import org.junit.Test;

import java.util.Arrays;

/**
 * 小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。
 * <p>
 * 注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,5,3,5], target = 6
 * <p>
 * 输出：1
 * <p>
 * 解释：预算内仅能购买 nums[0] 与 nums[2]。
 *
 * @author caijinnan
 */
public class LCP28采购方案 {

    @Test
    public void run() {
        int[] nums = {2, 5, 3, 5};
        int target = 11;
        System.out.println(purchasePlans(nums, target));
    }

    public int purchasePlans(int[] nums, int target) {
        int mod = 1000000007;
        Arrays.sort(nums);
        int count = 0;
        int left = 0;
        int right = nums.length - 1;
        int d = right;
        while (left < right) {
            if (nums[left] + nums[right] <= target) {
                count = (count + d) % mod;
                left++;
            } else {
                right--;
            }
            d--;
        }
        return count;
    }
}
